Complementarity restricts the accuracy with which incompatible quantum observables can be jointly measured. Despite popular conception, the Heisenberg uncertainty relation does not quantify this principle. We report the experimental verification of universally valid complementarity relations, including an improved relation derived here. We exploit Einstein-Poldolsky-Rosen correlations between two photonic qubits, to jointly measure incompatible observables of one. The product of our measurement inaccuracies is low enough to violate the widely used, but not universally valid, Arthurs-Kelly relation.